package heap.hard;

import java.util.PriorityQueue;

/**
 * 数据流的中位数
 * 例如，
 *
 * [2,3,4] 的中位数是 3
 *
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 *
 * 设计一个支持以下两种操作的数据结构：
 *
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 示例：
 *
 * addNum(1)
 * addNum(2)
 * findMedian() -> 1.5
 * addNum(3)
 * findMedian() -> 2
 *
 * 链接：https://leetcode-cn.com/problems/find-median-from-data-stream
 */
public class FindMedianFromDataStream_295 {

    //maxheap作为左堆，min作为右堆
    PriorityQueue<Integer> l = new PriorityQueue<>((a, b) -> b - a);
    PriorityQueue<Integer> r = new PriorityQueue<>();

    /**
     * if(两堆数量相同) {
     *     if(r为空 或者 num 小于或等于 r.peek())
     *     则添加到l堆
     *     else if num 大于r.peek()
     *     则把r的堆顶元素添加到l堆中，将num添加到r中
     * } else(两堆数量不同) {
     *     if(num >= l.peek())
     *     则直接添加到r中
     *     else(num < l.peek())
     *     则把l堆堆顶元素给添加到r中，num添加到l中。
     * }
     * @param num
     */
    public void addNum(int num) {
        if (l.size() == r.size()) {
            if (r.isEmpty() || num <= r.peek())
                l.offer(num);
            else {
                l.offer(r.poll());
                r.offer(num);
            }
        } else {
            if (num >= l.peek()) {
                r.offer(num);
            } else {
                r.offer(l.poll());
                l.offer(num);
            }
        }
    }
    public double findMedian() {
        if (l.size() == r.size())
            return (l.peek() + r.peek()) / 2;
        else
            return l.peek();
    }
}
